package com.LeetCode.Math;

import org.junit.Test;

/**
 * x的平方根
 */
public class Sqrt {

    /**
     * 牛顿开方法
     */
    public int mySqrt(int x) {
        long l = 0, r = x/2 + 1;
        while(l<r){
            long mid = (l+r+1)>>>1;
            long squre = mid * mid;
            if(squre > x){
                r = mid - 1;//往左收缩
            }else{
                l = mid;
            }
        }
        return (int)l;
    }

    public int sqrt (int x) {
        long r = x;
        while(r * r > x){
            r = (r + x / r) / 2;
        }
        return (int)r;
    }


    @Test
    public void test(){
        System.out.println(sqrt(4));
    }
}
